/**
 * 给你一个二维整数数组intervals，其中intervals[i] = [lefti, righti]表示 闭区间[lefti, righti]。
 *
 * 你需要将intervals 划分为一个或者多个区间组，每个区间 只属于一个组，且同一个组中任意两个区间 不相交。
 *
 * 请你返回 最少需要划分成多少个组。
 *
 * 如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交的。比方说区间[1, 5] 和[5, 8]相交。
 *
 * 链接：https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups
 */

/**
 * 给定一些区间段，按照一定的顺序将其分为n组，使得在n组中，每一个区间都不相交，返回n的最小数目
 *
 * 由于两区间段是否相交只取决于前一个区间的end和后一个区间的start
 *
 * start <= end则两个区间会相交
 *
 * 例如[1,4]和[3,5]
 *
 * 则可以维护一个区间end值的优先队列，每次一添加新的区间时，只需要贪心地选择最小的那个end值进行判断
 *
 * 若start > end则可以加入该分组中，并更新该分组的末尾
 *
 * 若start <= end则不可加入任何分组(这一点接下来会有详细的分析)，直接重新开一个分组，并将start对应的end加入其中
 *
 * 由于要求区间不可相交，则需要从start小的区间开始选取；因此需要对数组进行一个排序

 * 链接：https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/solution/by-endless_developy-soib/
 * 来源：力扣（LeetCode）
 */
class MinGroupsTanXin {
    public int minGroups(int[][] intervals) {
        Queue<Integer> qu=new PriorityQueue<>();
        Arrays.sort(intervals,(a,b)->{
            if(a[0]!=b[0]) return a[0]-b[0];
            else return a[1]-b[1];
        });
        for(int[] cur:intervals) {
            int left=cur[0],right=cur[1];
            if(qu.isEmpty()) {
                qu.offer(right);
            } else {
                if(left<=qu.peek()) {
                    qu.offer(right);
                } else {
                    qu.poll();
                    qu.offer(right);
                }
            }
        }
        return qu.size();
    }
}